Bằng chứng khảo cổ học cho các điệu nhảy thời kỳ đầu bao gồm những bức tranh 9.000 năm tuổi ở Ấn Độ tại Khu cư trú Đá Bhimbetka, và những bức tranh ở lăng mộ Ai Cập mô tả các hình tượng múa, có niên đại c. 3300 năm TCN. Người ta đã đề xuất rằng trước khi phát minh ra ngôn ngữ viết, khiêu vũ là một phần quan trọng trong các phương pháp truyền khẩu và biểu diễn để truyền lại những câu chuyện từ thế hệ này sang thế hệ khác.[6] Việc sử dụng khiêu vũ trong trạng thái xuất thần ngây ngất và các nghi lễ chữa bệnh (như được quan sát thấy ngày nay trong nhiều nền văn hóa "nguyên thủy" đương đại, từ rừng nhiệt đới Brazil đến sa mạc Kalahari) được cho là một yếu tố ban đầu khác trong sự phát triển xã hội của khiêu vũ.[7]

Các tài liệu tham khảo về khiêu vũ có thể được tìm thấy trong lịch sử được ghi chép rất sớm; Khiêu vũ Hy Lạp (horos) được Plato, Aristotle, Plutarch và Lucian nhắc đến.[8] Kinh thánh và Talmud đề cập đến nhiều sự kiện liên quan đến khiêu vũ, và chứa hơn 30 thuật ngữ khiêu vũ khác nhau.[9] Trong đồ gốm Trung Quốc ngay từ thời kỳ đồ đá mới, các nhóm người được miêu tả đang nhảy múa trong một hàng nắm tay nhau,[10] và từ tiếng Trung sớm nhất có nghĩa là "khiêu vũ" được tìm thấy trong xương dùng để bói toán.[11] Vũ điệu được mô tả kỹ hơn trong tác phẩm Lã thị Xuân Thu.[12][13] Múa nguyên thủy ở Trung Quốc cổ đại gắn liền với các nghi lễ ma thuật và phù thủy.[14]

Trong thiên niên kỷ đầu tiên trước Công nguyên ở Ấn Độ, nhiều văn bản đã được viết ra nhằm cố gắng hệ thống hóa các khía cạnh của cuộc sống hàng ngày. Natyashastra của Bharata Muni (nghĩa đen là "văn bản của nghi lễ kịch") là một trong những văn bản trước đó. Nó chủ yếu đề cập đến kịch, trong đó khiêu vũ đóng một phần quan trọng trong văn hóa Ấn Độ. Nó phân loại khiêu vũ thành bốn loại - thế tục, nghi lễ, trừu tượng và, diễn giải - và thành bốn loại khu vực. Văn bản trình bày chi tiết các cử chỉ tay khác nhau (mudras) và phân loại các chuyển động của các chi, các bước khác nhau, v.v. Truyền thống khiêu vũ liên tục mạnh mẽ kể từ đó đã tiếp tục ở Ấn Độ, cho đến thời hiện đại, nơi nó tiếp tục đóng một vai trò trong văn hóa, nghi lễ và đặc biệt là ngành công nghiệp giải trí Bollywood. Nhiều hình thức múa đương đại khác cũng có thể bắt nguồn từ các điệu múa lịch sử, truyền thống, nghi lễ và dân tộc.